:- module(match,
	[
%           match/7,
%	    match_list/5,
%	    match_sort_list/6,
	    match_sort_interval_list/10,
	    match_mode/1,
	    match_sort_result/1,
	    sort_method/1
%	    generalize/6,
%	    generalize_strict/4,
%	    specialize/2,
%	    inverse_deps/3
        ], [.(package_ops),dcg, assertions,regtypes,basicmodes]).

%% To select the database to use.
:- include(which_match_to_use).

:- use_module(library(sets)).
:- use_module(library(hiordlib)).
:- use_module(library(sort), [keysort/2,sort/2]).
:- use_module(library(lists), [append/3,length/2]).
%:- use_module(library(aggregates), [findall/3,setof/3]).
:- use_module(library(aggregates)).
:- use_module(library(dict)).
:- use_module(search(utils)).
:- use_module(library(prolog_sys), [statistics/2]).

:- initialization(gen_inverse_deps).

:- comment(module, "This module contains the implementation of the
   matching engine. Given a query expressed in the Amos internal
   language, it produces a list of packages that satisfy the query.

   @newpage

").

%log_message(_).

% inverse_deps(Package,Rules)
% Inverse dependency info. For each package name @var{Package},
% @var{Rules} is the list of rules where @var{Package} appears
% as a Postcondition.
:- data inverse_deps/3.

% Generates inverse dependency info on inverse_deps/3 procedure,
% getting for each package the list of rules where it appears for
% every level of generalization.
gen_inverse_deps :-
        ThisPackage := _Prec ==> Post,
	member(Capability, Post),
	(
            retract_fact(inverse_deps(Capability, PackageList, 0)) ->
            true
	; 
	    PackageList = []
	),
	insert(PackageList, ThisPackage, NewPackList),
	assertz_fact(inverse_deps(Capability, NewPackList, 0)),
	fail.
gen_inverse_deps:-
	max_generalization(Max),
	gen_inverse_deps_gen(Max).

max_generalization(0). %% IMPORTANT: this must match with the maximum generalization level in form_page.pl.

:- data continue/0.

% Generates inverse dependency info on inverse_deps/3 procedure,
% taking generalizations into account
gen_inverse_deps_gen(Max) :-
	retractall_fact(continue),
	gen_inverse_deps_gen_1(Max),
	(
	    continue ->
	    gen_inverse_deps_gen(Max)
	;
	    remove_intersections(Max)
	).

%% Generates inverse deps for generalizations
gen_inverse_deps_gen_1(Max) :-
%	term_desc(Capability,_Desc,Gens),
	term_desc_keys(CapKey,_Desc,Gens),
	member(GenKey,Gens),
	inverse_deps(GenKey,GenPkgList,N),
	N < Max,
	N1 is N + 1,
	(
	    current_fact(inverse_deps(CapKey, PackageList, N1),Ref) ->
	    erase(Ref),
	    ord_union(PackageList, GenPkgList, NewPackList),
	    assertz_fact(inverse_deps(CapKey, NewPackList, N1)),
	    ( N1 < Max, \+ PackageList = NewPackList -> set_fact(continue) ; true)
	; 
	    assertz_fact(inverse_deps(CapKey, GenPkgList, N1)),
	    ( N1 < Max -> set_fact(continue) ; true)
	),
	fail.
gen_inverse_deps_gen_1(_Max).

%% Removes intersections between different generalization levels of each term.
remove_intersections(Max) :-
	current_fact(inverse_deps(Term,Pkg0,0)),
	remove_intersections_1(Term,Pkg0,1,Max),
	fail.

remove_intersections_1(_Term,_Pkg0,Max,Max).
remove_intersections_1(Term,Pkg0,Min,Max) :-
	( 
	    retract_fact(inverse_deps(Term,Pkg1,Min)) ->
	    ord_subtract(Pkg1,Pkg0,NewPkg1),
	    asserta_fact(inverse_deps(Term,NewPkg1,Min)),
	    Min1 is Min + 1,
	    ord_union(Pkg1,Pkg0,UnionPkg),
	    remove_intersections_1(Term,UnionPkg,Min1,Max)
	;
	    true
	), !.


% db_match/7 prepares things to work with match/7:
%  - gets the keys of Wanted, IncPack and ExcPack
%  - calls match/7
%  - gets the names for Flooded, Capabilities and Packages. 

match_list(Mode,Wanted,Timeout,IncPack,ExcPack,MatchList) :-
	ditem_name_to_key(Wanted,WantedK),
	resource_name_to_key(IncPack,IncPackK),
	resource_name_to_key(ExcPack,ExcPackK),
	findall(
		 match_result(Flooded,Capabilities,Packages),
		 (
%   FloodedK^CapabilitiesK^PackagesK^
		 (internal_match(Mode, WantedK, Timeout, FloodedK, CapabilitiesK, PackagesK, IncPackK, ExcPackK),
		  ditem_pair_key_to_name(Flooded,FloodedK),
		  ditem_pair_key_to_name(Capabilities,CapabilitiesK),
		  resource_key_to_name(Packages,PackagesK))
% put here a comma and remove a parenthesis... log_message(resource_to_name_ok))
		 ),MatchList0
	     ) -> sort(MatchList0,MatchList)
 ;
	MatchList=[].

ditem_pair_key_to_name([], []).
ditem_pair_key_to_name([(C0, L0)|Pairs0], [(C, L)|Pairs]) :-
	ditem_key_to_name([C0], [C]),
	caphistory_key_to_name(L0, L),
	ditem_pair_key_to_name(Pairs0, Pairs).

caphistory_key_to_name([], []).
caphistory_key_to_name([h(T,C0)|Hs0], [h(T,C)|Hs]) :-
	ditem_key_to_name([C0], [C]),
	caphistory_key_to_name(Hs0, Hs).

interval_list(A,Ini,Len,L) :-
	( skip(Ini, A, A2) ->
	    ( take(Len, A2, L) ->
	        true
	    ; L = A2
	    )
	; L = []
	).

skip(I, Xs, Xs) :- I =< 0, !.
skip(I, [_|Ys], Xs) :-
	I1 is I - 1,
	skip(I1, Ys, Xs).

take(I, _, []) :- I =< 0, !.
take(I, [X|Ys], [X|Xs]) :-
	I1 is I - 1,
	take(I1, Ys, Xs).

match_sort_list(SortMethod, Mode, Wanted, Timeout, IncPack, ExcPack, MatchList):-
	match_list(Mode, Wanted, Timeout, IncPack, ExcPack, UnsortedMatch),
	(   UnsortedMatch = [] ->
	    MatchList = []
	;
	    match_sort_results(SortMethod, Wanted, UnsortedMatch, MatchList)
	).

% ---------------------------------------------------------------------------

:- regtype match_mode(X) 

# "@var{X} Matching modes available in the search
  engine. Available modes can be:
@begin{itemize}
 @item @tt{all} returns all the assemblies which match the query.

 @item @tt{best(N)} selects the best @tt{N} assemblies which
   satisfy the query.

 @item @tt{gen(N,M)} extends the matching of assemblies taking into
   account possible generalizations: @tt{N} determines the maximum
   level of generalizations in preconditions (the description terms
   that a package requires), while @tt{M} specifies the level of
   generalizations in postconditions (terms that a package
   provides).
@end{itemize}
".

match_mode(all).
match_mode(best(N)) :- num(N).
match_mode(gen(Pre, Post)) :- num(Pre), num(Post).

% ---------------------------------------------------------------------------

:- regtype sort_method(X) 

# "@var{X} Weights assigned for the different sort
   options in the internal query language.".

:- comment(sort_method/1,"@includedef{sort_method/1}").

sort_method(key_weights(P, U, T, C, B)) :-
	weight__package_number(P),
        weight__unsatisfied_deps(U),
	weight__tighter_assemblies(T),
	weight__capabilities(C),
	weight__best_capabilities_ratio(B).

:- export(weight__package_number/1).
:- regtype weight__package_number(X) 

# "@var{X} Weight assigned to the number of packages provided
  by the matching engine.".

weight__package_number(X) :- num(X).

:- export(weight__unsatisfied_deps/1).
:- regtype weight__unsatisfied_deps(X) 

# "@var{X} Weight assigned to the number of unsatisfied
  dependencies (less dependencies get higher weights).".

weight__unsatisfied_deps(X) :- num(X).

:- export(weight__tighter_assemblies/1).
:- regtype weight__tighter_assemblies(X) 

# "@var{X} Weight assigned to the number of tighter
  assemblies (looser assemblies get higher weights).".

weight__tighter_assemblies(X) :- num(X).

:- export(weight__capabilities/1).
:- regtype weight__capabilities(X) 

# "@var{X} Weight for number of capabilities.".

weight__capabilities(X) :- num(X).

:- export(weight__best_capabilities_ratio/1).
:- regtype weight__best_capabilities_ratio(X) 

# "@var{X} Weight assigned to the ratio satisfied/unsatisfied
  capabilities.".

weight__best_capabilities_ratio(X) :- num(X).

% ---------------------------------------------------------------------------

:- regtype match_sort_result(X) 

# "@var{X} Sorted result of a search".

:- comment(match_sort_result/1,"@includedef{match_sort_result/1}").

match_sort_result(X) :-
	list(match_result_key, X).

:- regtype match_result_key(X).
march_result_key(Key-MatchResult) :-
	match_key(Key),
	match_result(MatchResult).

:- regtype match_key(X) # "@var(X) is the weight of an assembly". % score?
:- comment(match_key/1,"@includedef{match_key/1}").
match_key(X) :- num(X).

:- regtype match_result(X) # "@var(X) is an assembly".
:- comment(match_result/1,"@includedef{match_result/1}").
match_result(match_result(Flooded, Capabilities, Packages)) :-
	list(capability, Flooded),
	list(capability, Capabilities),
	list(package, Packages).

:- export(package/1).
:- regtype package(X) # "@var{X} is a Amos package".
package(X) :- atm(X).

:- export(capability/1).
:- regtype capability(X) # "@var{X} is a Amos capability".
capability(X) :- atm(X).

% ---------------------------------------------------------------------------

:- true pred match_sort_interval_list(in(SortMethod), in(Mode),
   in(Wanted), in(IncPack), in(ExcPack), in(Ini), in(Len),
   go(MatchList), go(Total)) :: sort_method * match_mode * list * list
   * list * int * int * match_sort_result * int 

 # "This is the main procedure for performing a search expressed in
   the internal language. This procedure generates a list
   @var{MatchList} containing the resulting assemblies of a given
   query. A query is expressed in the internal query language, and is
   defined as follows:

@begin{itemize}
 @item @var{SortMethod} specifies the sorting method used for the
   query. Several values are allowed, as described in
   @pred{sort_method/1}.

 @item @var{Mode} selects the search type. Allowed values are
   described in @pred{match_mode/1}.

 @item @var{Wanted} is the list of capabilities to search. It must be
   provided to the matching engine as a list of description terms.

 @item @var{IncPack} allows to specify that the results of the
   matching engine must contain a mandatory set of packages,
   represented by a list of package names. If there are no packages to
   include, @var{IncPack} must be an empty list.

 @item In the same way, @var{ExcPack} specifies a (possibly empty)
   list of packages which should not appear in the resulting
   assemblies given by the matching engine.
@end{itemize}

   The assemblies provided by the matching engine that satisfy the
   query are sorted using the criteria specified in @var{SortMethod},
   and returned in subsets of length @var{Len}, starting with the
   @var{Ini}th element of the complete results list (the first element
   of the list is numbered 0). In @var{Total}  the total
   number of results found is returned.".


match_sort_interval_list(SortMethod, Mode, Wanted, Timeout, IncPack, ExcPack,
	Ini, Len, MatchList, Total) :-
	match_sort_list(SortMethod, Mode, Wanted, Timeout, IncPack, ExcPack, MatchList0),
%	log_message(interval_list_begin),
	length(MatchList0, Total),
	interval_list(MatchList0, Ini, Len, MatchList).
%...	log_message(interval_list_end).

match_sort_results(KeyWeights, Wanted, UnsortedMatch, SortedMatch) :-
%	log_message(match_sort_results(KeyWeights, Wanted, UnsortedMatch, SortedMatch)),
	get_package_number_list(KeyWeights, Wanted, UnsortedMatch,KeyList),
%	log_message(keysort(KeyList,SortedMatch)),
	keysort(KeyList,SortedMatchAbs),
	match_relativize_key(SortedMatchAbs,SortedMatch).
%...	log_message(match_sort_results_ok).

max_key([MaxKey-_M],MaxKey).
max_key([_K|Ks],MaxKey) :-
	max_key(Ks,MaxKey).

min_key([K-_M|_Ks],K).

match_relativize_key(MatchListAbs,MatchListRel) :-
	min_key(MatchListAbs,Key0),
	max_key(MatchListAbs,KeyN),
	(
	    KeyN = Key0 ->
	    DKey = 1
	;
	    DKey is KeyN-Key0
	),
	length(MatchListAbs,N),
	match_relativize_key_2(N,DKey,Key0,MatchListAbs,MatchListRel).

match_relativize_key_2(_,_,_,[],[]).
match_relativize_key_2(N, DKey, Key0,[Key-Match|MatchListAbs], [RelKey-Match|MatchListRel]) :-
	RelKey is 1-((N-1)/N)*((Key-Key0)/DKey),
	match_relativize_key_2(N, DKey, Key0,MatchListAbs,MatchListRel).

% this procedure gives the sort key based on some factors:
get_key_for_sort(
	key_weights(
	       WPackageNumber,                   % Weight for number of packages
	       WUnsatisfiedDeps,                 % Weight for number of unsatisfied dependencies
	       WTighterAssemblies,               % Weight for number of tighter assemblies
	       WCapabilities,                    % Weight for number of capabilities
	       WBestCapabilitiesRatio),          % Weight for ratio unsat/satisfied (less values are better)
	Wanted,
        match_result(
		Flooded,
		Capabilities,
		Packages),
	Key) :-

        length(Packages, NPackageNumber),
	length(Flooded, NUnsatisfiedDeps),
	ord_subtract(Capabilities,Wanted,RedundantCaps),
	length(RedundantCaps, NRedundantCaps),
	length(Capabilities, NCapabilities),
	Key is
             -(+ NPackageNumber*WPackageNumber
             + NUnsatisfiedDeps*WUnsatisfiedDeps
             + NRedundantCaps*WTighterAssemblies
             + NCapabilities*WCapabilities     
             + (NCapabilities/(NUnsatisfiedDeps+1))*WBestCapabilitiesRatio)
        .

get_package_number_list(_KeyWeights,_Wanted,[],[]).
get_package_number_list(KeyWeights, Wanted, [Match|MatchList], [Key-Match|KeyList]) :-
	get_key_for_sort(KeyWeights, Wanted, Match, Key),
	get_package_number_list(KeyWeights, Wanted, MatchList, KeyList).

 % match(Wanted, Selection, Packages, Flooded): Wanted capabilites are
 % sought for in the database of packages.  Selection is the set of
 % capabilities fulfilled by the Packages selected, and Flooded is the
 % set of unmatched capabilities.
internal_match(Mode, Wanted, Timeout, Flooded, Capabilities, Packages, IncPack, ExcPack):-
	statistics(walltime, [T|_]),
	MaxT is T + Timeout,
%	log_message(match(Mode, Wanted, Flooded, Capabilities, Packages, IncPack, ExcPack)),

 %% (
 %%           Mode = reduce(_) ->                 % Make sure the DB is empty
 %%         clean_up_db(Mode)                   % (in case of, e.g., interrp.)
 %%         ;
 %%             true
 %%         ),
        sort(IncPack, IncPackSorted),
        sort(ExcPack, ExcludedPackagesSorted),
        initial_capabilities_demands(IncPackSorted, IniCap, IniReq),
        sort(Wanted, SetOfWanted),
        ord_union(SetOfWanted, IniReq, ReallyWanted),

	S0 = s(ReallyWanted, [], [], IniCap, [], _Dic0, IncPackSorted),
        catch(match_accm(Mode, ExcludedPackagesSorted, MaxT, S0, S),
	      timeout, fail),
	S = s(_, _, _, Capabilities1, Flooded1, Dic, Packages),
	pair_caps(Capabilities1, Dic, Capabilities),
	pair_caps(Flooded1, Dic, Flooded),
	\+ (Packages = []).
%	remove previous point ... log_message(match_ok).

pair_caps([], _, []).
pair_caps([C|Cs], Dic, [(C,L)|Pairs]) :-
	req_c(Dic, C, c(_,_,L)),
	pair_caps(Cs, Dic, Pairs).

initial_capabilities_demands(IncPack, IniCap, IniReq):-
        findall(CapSort,
                (
                    member(Pack, IncPack), 
                    Pack := _ ==> Cap,
                    sort(Cap, CapSort)
                ), ListOfCaps),
        sort(ListOfCaps, SetsOfCaps),
        foldl(SetsOfCaps, [], ord_union, IniCap),
        findall(ReqSort,
                (
                    member(Pack, IncPack), 
                    Pack := Req ==> _,
                    sort(Req, ReqSort)
                ), ListOfReqs),
        sort(ListOfReqs, SetsOfReqs),
        foldl(SetsOfReqs, [], ord_union, IniReq).


 % Update the Wanted capabilities by reducing them with Packages.  We
 % keep track of the accumulated Capabilities in order to discard them
 % from capabilities needed by every package.  When no package is able
 % to reduce the set of Wanted capabilities, the search finishes.

 % A necessary condition is: intersection(Wanted, Capabilities, []).

match_accm(_, _, MaxT, _, _) :-
	statistics(walltime, [T|_]),
	T > MaxT, !, throw(timeout).
match_accm(_Mode, _ExcludedPacks, _MaxT, S, S) :-
	S = s(Pending, GenPending, _Visited, _Caps, _Flooded, _Dic, _Packs),
        Pending = [],
        GenPending = [], !.
match_accm(Mode, ExcludedPacks, MaxT, S0, S) :-
	S0 = s(Pending0, GenPending, Visited0, Caps0, Flooded0, Dic0, Packs0),
        Pending0 = [], !,
	ord_union(Visited0, GenPending, Visited),
	generalize_reql(GenPending, Mode, Dic0, Dic1, [], Pending1),
	ord_subtract(Pending1, Visited, Pending),
	S1 = s(Pending, [], Visited, Caps0, Flooded0, Dic1, Packs0),
        match_accm(Mode, ExcludedPacks, MaxT, S1, S).
match_accm(Mode, ExcludedPacks, MaxT, S0, S) :-
        % Find a rule which provides some of the pending
        % capabilities.  There is room here for to express:
        % which capabilities are to be "reduced" (probably we
        % want to reduce as much as possible), and which package
        % matching some of these capabilities is to be used (selection
        % based on some kind of metric).
        select_rule(Mode, ExcludedPacks, S0, S1),
        match_accm(Mode, ExcludedPacks, MaxT, S1, S).

 % Select rule should (naturally) be a constructive negation of the
 % termination rule --- or rather, the other way around.
 % The formulae here can surely be simplified --- apart from sped up
 % by using some smart ordering.

 % The code here assumes that if P := A ==> B, then intersection(A,B,[])

 % Simple selection rule: just retrieve all matches.  Not useful for an
 % non-interactive execution.

%efm-begin

% in2out([],[]).
% in2out([in(X)|Is],[out(X)|Os]):-!,
% 	in2out(Is,Os).
% in2out([X|Is],[X|Os]) :-!,
% 	in2out(Is,Os).

% selectout([],[]).
% selectout([out(X)|Os],[out(X)|Fs]):-!,
% 	selectout(Os,Fs).
% selectout([_O|Os],Fs) :-!,
% 	selectout(Os,Fs).

%efm-end

generalize_strict_(Level,P,Pending) :-
	Level = 0 ->
	member(P,Pending)
 ;
	(
	    Level > 0 ->
	    Level1 is Level-1,
	    member(P0,Pending),
%	    term_desc(P0,_,GenList),
	    term_desc_keys(P0,_,GenList),
	    generalize_strict_(Level1,P,GenList)
	;
	    fail
	).

generalize_strict(Level,P0,P,Pending) :-
	Level = 0 ->
	member(P0,Pending),
	P=P0
 ;
	(
	    Level > 0 ->
	    Level1 is Level-1,
	    member(P0,Pending),
	    term_desc_keys(P0,_,GenList),
	    generalize_strict_(Level1,P,GenList)
	;
	    fail
	).

count(Min,Max,X) :-
	Min > Max -> fail
 ;
	(
	    X=Min
	;
	    Min2 is Min+1,
	    count(Min2,Max,X)
	).

generalize(MinLevel,MaxLevel,L,P0,P,Pending) :-
	count(MinLevel,MaxLevel,L),
	generalize_strict(L,P0,P,Pending).

% generalize(MinLevel,Level,L,P0,P,Pending) :-
% 	Level < MinLevel -> fail
%  ;
% 	(
% 	    Level1 is Level-1,
% 	    generalize(MinLevel,Level1,L,P0,P,Pending)
% 	;
% 	    generalize_strict(Level,P0,P,Pending),
% 	    L = Level
% 	).

% Only needs 1 specialization level:
specialize(P,Q) :-
	Q=P
 ;
	term_desc_keys(Q,_,G),
	member(P,G).
% uncomenting next line will cause specialize work recursively:
%	specialize(Q0,Q).

% note that select_rule(all ... = select_rule(gen(0,0) ...

% The notation of generalization match mode is gen(LevelPrec,LevelPost).
% LevelPending is the Level of generalization applied to the pending
% capabilities to fit.  LevelPrec is the Level of generalization applied
% to the Preconditions and LevelPost is the Level of generalization
% applied to the Postconditions.  Like it was to be expected, gen(0,0)
% behaves just as 'all' mode.

% Note that LevelPrec could be logically incorrect and can introduce
% errors in the search.
/* old code
select_rule(gen(LevelPrec,LevelPost), Pending, Caps, NewPend, NewCaps, Pack):-
%        log_message(s_r(Pending, Caps, NewPend, NewCaps, Pack)),

	member(P0,Pending),
%	generalize(0,LevelPrec,_,P0,P1,Pending),

	specialize(P0,P2),

	count(0,LevelPost,X),
	inverse_deps(P2,Packs,X),
	member(Pack,Packs),

	Pack := Prec0 ==> Post,

%	findall(PostOne,generalize(0,LevelPost,_LevelPost0,P2,PostOne,Post0),PostGen),
%	\+(PostGen = []),
%	sort(PostGen,Post),

%	member(P,Post),

	findall(PrecOne,generalize(0,LevelPrec,_LevelPrec0,_Prec0,PrecOne,Prec0),PrecGen),
	sort(PrecGen,Prec),

%	(   P=stream(_Stream) ->
%	    selectnostream(Post,Post2),
%	    ord_union(Post2, Caps, NewCaps)
%	;
	    NewCaps0=NewCaps,
%	),
        % Parts of the rule preconditions might be already fulfilled
        % Caps can be used instead of NewCaps if inters(Prec,Post,[])
	% The pending capabilities can now be reduced

	ord_union(Post,Caps,NewCaps0),

	% Note that subtract P0 is an aproximation and will introduce
	% logically false responses.

	ord_subtract(Prec, NewCaps0, RealPrec),
	ord_subtract(Pending, [P0|Post], RealPending),
	ord_union(RealPending, RealPrec, NewPend).
*/

select_rule(Mode, ExcludedPacks, S0, S) :-
%        log_message(s_r(Pending, Caps, NewPend, NewCaps, Pack)),
	S0 = s(Pending, GenPending, Visited, Caps, Flooded, Dic, Packs),
	Pending = [P0|Pending2],
	P0 = P2,
	( inverse_deps(P2,P2Packs,0) ->
	    member(Pack,P2Packs),
	    Pack := Prec ==> Post,
	    ord_test_member(ExcludedPacks, Pack, no),
	    ord_union(Post,Caps,NewCaps),
	    ord_subtract(Prec, NewCaps, RealPrec),
	    ord_subtract(Pending2, Post, RealPending),
	    ord_union(RealPending, RealPrec, NewPend),
	    GenPending = NewGenPending,
	    Flooded = NewFlooded,
	    insert(Packs, Pack, NewPacks)
	; final_req(P2, Mode, Dic) ->
            Pending2 = NewPend,
	    GenPending = NewGenPending,
	    Caps = NewCaps,
	    insert(Flooded, P2, NewFlooded),
	    Packs = NewPacks
	; insert(GenPending, P2, NewGenPending),
          Pending2 = NewPend,
	  Caps = NewCaps,
	  Flooded = NewFlooded,
	  Packs = NewPacks
	),
	S = s(NewPend, NewGenPending, Visited, NewCaps, NewFlooded, Dic, NewPacks).

final_req(P, Mode, Dic) :-
	\+ generalize_req(P, Mode, Dic, _, _).

gen(P1, P2) :-
	term_desc_keys(P1,_,G),
	member(P2,G).

spe(P1, P2) :- gen(P2,P1). % todo: improve...

% gen/spec a list of capabilities (nondet!)
generalize_reql([], _Mode, Dic, Dic, Pending,Pending) :- !.
generalize_reql([P|GenPending], Mode, Dic0, Dic, Pending0,Pending) :-
	generalize_req(P,Mode,Dic0,Dic1,P1),
	insert(Pending0,P1,Pending1),
	generalize_reql(GenPending, Mode, Dic1,Dic,Pending1,Pending).

generalize_req(P, Mode, Dic, Dic2, P2) :-
	req_c(Dic, P, C),
	C = c(CPrec,CPost,L),
	Mode = gen(LevelPrec,LevelPost),
	( CPost < LevelPost, CPost1 is CPost + 1, spe(P, P2), C2 = c(CPrec, CPost1, [h(spe, P)|L])
	; CPrec < LevelPrec, CPrec1 is CPrec + 1, gen(P, P2), C2 = c(CPrec1, CPost, [h(gen, P)|L])
	),
	dic_replace(Dic, P2, C2, Dic2).

req_c(Dic, P, C) :-
	( dic_get(Dic, P, C) ->
	    true
	; C = c(0,0,[])
	).

 % Backtrack over all packages which contribute to reducing the set of
 % required capabilities and find out the length of the reduced set of
 % pending capabilities.  Return also the reduced set, so that it does
 % not have to be recomputed.
ordered_set_of_matches(Pending, 
                       Pack := Prec ==> Post,
                       RealPending,
                       PendLength):-
        Pack := Prec ==> Post,
	ord_intersection(Post, Pending, [_|_]), % this one contributes
	ord_subtract(Pending, Post, RealPending),
	length(RealPending, PendLength).


 % Get the best N
get_best_n(OrderedList, N, BestN):-
        % Use the local value as starting point
        OrderedList = [ThisLen-_|_],
	get_best(OrderedList, N, ThisLen, BestN).

 % End of list: just stop
get_best([], _N, _Len, []).
 % Otherwise: if we did not change length, go on
get_best(_List, 0, _PrevLen,  []):- !.
get_best([Len-Pack|Packs], N, PrevLen, List):-
	(
	    Len > PrevLen ->                    % Change level only
	    N1 is N - 1,
	    get_best([Len-Pack|Packs], N1, Len, List)
	;
	    List = [Len-Pack|Rest],
	    get_best(Packs, N, PrevLen, Rest)
	).
